6387. Острова в потоке данных

Маленькие Дима и Петя хотят организовать соревнование. Их маленькие друзья выслали Задана последовательность целых чисел a₁, a₂, a₃, ..., a_n. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

Напишите программу, на вход которой поступает последовательность из 15 неотрицательных целых чисел, где каждое число отличается от предыдущего не более чем на 1, и выводит количество островов в последовательности.

Вход. Первая строка содержит количество тестов p (1 ≤ p ≤ 1000).

Каждый тест состоит из одной строки. Она содержит номер теста k, за которым следует 15 неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны 0. Каждое число отличается от предыдущего не более чем на 1.

Выход. Для каждого теста выведите в отдельной строке его номер k, пробел, и количество островов в последовательности.

Пример входа	Пример выхода
4 1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0 2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0	1 4 2 7 3 7 4 7

РЕШЕНИЕ

обработка последовательностей

Анализ алгоритма

Количество островов равно числу таких индексов i, для которых a_i < a_i+1. Это следует из структуры последовательности.

Реализация алгоритма

Последовательно обрабатываем тесты.

scanf("%d",&tests);

for(i = 1; i <= tests; i++)

{

В переменной cnt подсчитываем количество таких индексов i, для которых prev = a_i < a_i+1 = cur.

cnt = 0;

Сначала в prev читаем номер теста (больший нуля), за которым сразу идет cur = 0.

scanf("%d",&prev);

for(j = 1; j <= 15; j++)

{

scanf("%d",&cur);

if (prev < cur) cnt++;

prev = cur;

}

Выводим ответ.

printf("%d %d\n",i,cnt);

}